package 代码随想录.二叉树;

import java.util.LinkedList;
import java.util.Queue;

public class _8对称二叉树 {
    /**
     * 101. 对称二叉树
     * https://leetcode.cn/problems/symmetric-tree/
     * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
     */
    public boolean isSymmetric(TreeNode root) {
        return isTrue(root,root);
    }
    boolean isTrue(TreeNode root1,TreeNode root2){
        if(root1==null && root2==null)
            return true;
        if(root1==null || root2==null || root2.val!= root1.val)
            return false;
        return isTrue(root1.left,root2.right) && isTrue(root1.right,root2.left);
    }

    //迭代法
    public boolean isSymmetric3(TreeNode root) {
        Queue<TreeNode> deque = new LinkedList<>();
        deque.offer(root.left);
        deque.offer(root.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.poll();
            TreeNode rightNode = deque.poll();
            if (leftNode == null && rightNode == null) {
                continue;
            }
            // 以上三个判断条件合并
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false;
            }
            deque.offer(leftNode.left);
            deque.offer(rightNode.right);
            deque.offer(leftNode.right);
            deque.offer(rightNode.left);
        }
        return true;
    }

    /**
     * 100. 相同的树
     * https://leetcode.cn/problems/same-tree/
     * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
     * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
     */
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> deque1 = new LinkedList<>();
        Queue<TreeNode> deque2 = new LinkedList<>();
        if(p==null && q==null)
            return true;
        if(p==null || q==null)
            return false;
        deque1.offer(p);
        deque2.offer(q);
        while (!deque1.isEmpty() || !deque2.isEmpty()){
            TreeNode node1 = deque1.poll();
            TreeNode node2 = deque2.poll();
            if(node1==null&&node2==null)
                continue;
            if(node1==null || node2==null || node1.val!=node2.val)
                return false;
            deque1.offer(node1.left);
            deque2.offer(node2.left);
            deque1.offer(node1.right);
            deque2.offer(node2.right);
        }
        return true;
    }

    public boolean isSameTree2(TreeNode p, TreeNode q) {
        return compare(p,q);
    }
    boolean compare(TreeNode p, TreeNode q){
        if(p==null && q==null)
            return true;
        if(p==null || q==null || p.val!=q.val)
            return false;
        return compare(p.left,q.left) && compare(p.right,q.right);
    }

    /**
     * 572. 另一棵树的子树
     * https://leetcode.cn/problems/subtree-of-another-tree/
     * 给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在，返回 true ；否则，返回 false 。
     * 二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        boolean flag = compare2(root,subRoot);
        if((root==null && subRoot==null) || flag)
            return true;
        if(root==null || subRoot==null )
            return false;
        return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }
    boolean compare2(TreeNode p, TreeNode q){
        if(p==null && q==null)
            return true;
        if(p==null || q==null || p.val!=q.val)
            return false;
        return compare(p.left,q.left) && compare(p.right,q.right);
    }

    public boolean isSubtree2(TreeNode root, TreeNode subRoot) {
        //空树不为子结构
        if(root == null || subRoot == null)
            return false;
        Queue<TreeNode> q = new LinkedList<TreeNode>();
        q.offer(root);
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            //遇到与树2根相同的节点，以这个节点为根判断后续子树是否相同
            if(node.val == subRoot.val){
                if(helper(node, subRoot))
                    return true;
            }
            //左子树入队
            if(node.left != null)
                q.offer(node.left);
            //右子树入队
            if(node.right != null)
                q.offer(node.right);
        }
        return false;
    }
    private boolean helper(TreeNode root1, TreeNode root2){
        Queue<TreeNode> q1 = new LinkedList<TreeNode>();
        Queue<TreeNode> q2 = new LinkedList<TreeNode>();
        q1.offer(root1);
        q2.offer(root2);
        //以树2为基础，树1跟随就可以了
        while(!q2.isEmpty()){
            TreeNode node1 = q1.poll();
            TreeNode node2 = q2.poll();
            //树1为空或者二者不相等
            if(node1 == null || node1.val != node2.val)
                return false;
            //树2还有左子树
            if(node2.left != null){
                //子树入队
                q1.offer(node1.left);
                q2.offer(node2.left);
            }
            //树2还有右子树
            if(node2.right != null){
                //子树入队
                q1.offer(node1.right);
                q2.offer(node2.right);
            }
        }
        return true;
    }
}
